/*
设计一个算法，判断一棵二叉排序树bt是否为平衡二叉排序树。

【输入形式】

一行，第一行为空格分隔的多个数字，最后以0表示输入结束。

【输出形式】

true或者false，如果输入数据构成的二叉树是平衡的，输出true, 否则，输出false
*/

#include <iostream>

#include <stack>

#include <queue>

using namespace std;

typedef struct BSTNode{

    int data;

    struct BSTNode *lchild, *rchild;

}BSTNode, *BSTree;



void InsertBST(BSTree &T, int x)//插入二叉排序树

{

    if(!T)//空树

    {

        BSTree p;

        p = new BSTNode;//新二叉排序树结点

        p->data = x;

        p->lchild = p->rchild = NULL;

        T = p;

    }

    else if(x < T->data)

        InsertBST(T->lchild, x);//小的为左孩子

    else if(x > T->data)

        InsertBST(T->rchild, x);//大的为右孩子

}



void CreateBST(BSTree &T)//建立二叉排序树

{

    T = NULL;

    int x;

    cin>>x;

    while(x != 0)

    {

        InsertBST(T, x);

        cin>>x;

    }

}



void ldroutput(BSTree T,int x)//中序遍历二叉排序树为从小到大顺序

{//从小到大输出二叉排序树中所有数值大于等于x的结点的数据

    if(T)

    {

        ldroutput(T->lchild,x);

        if(T->data>=x)

            cout << T->data << " ";

        ldroutput(T->rchild,x);

    }

}



int depth(BSTree T)//二叉树深度

{

    int m = 0, n = 0;

    if(T==NULL)//空树

        return 0;

    else

    {

        m=depth(T->lchild);//左孩子深度

        n=depth(T->rchild);//右孩子深度

        if(m>n)

            return m + 1;

        else

            return n + 1;

    }

}



int anvtree(BSTree T)

{

    if(T==NULL)//空树平衡

        return 1;

    int l, r;

    l = depth(T->lchild);

    r = depth(T->rchild);

    if((l-r)>1||(l-r)<-1)//不平衡

        return 0;

    return anvtree(T->lchild) && anvtree(T->rchild);

}



int main()

{

    BSTree T;

    CreateBST(T);//创建二叉排序树

    if(anvtree(T))

        cout << "true";

    else

        cout << "false";

    return 0;

}